//给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。 
//
// 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列
//，而 "AEC" 不是） 
//
// 题目数据保证答案符合 32 位带符号整数范围。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "rabbbit", t = "rabbit"
//输出：3
//解释：
//如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
//rabbbit
//rabbbit
//rabbbit 
//
// 示例 2： 
//
// 
//输入：s = "babgbag", t = "bag"
//输出：5
//解释：
//如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
//babgbag
//babgbag
//babgbag
//babgbag
//babgbag
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length, t.length <= 1000 
// s 和 t 由英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 803 👎 0


package leetcode.editor.cn;

/**
 * 不同的子序列
 * @date 2022-07-04 09:51:55
 */
class P115_DistinctSubsequences{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P115_DistinctSubsequences().new Solution();
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int numDistinct(String s, String t) {
		/**
		 * 1：为啥状态方程是： s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
		 *
		 * 					s[i] != t[j] 时 dp[i][j] = dp[i-1][j]
		 *
		 * 先看s[i] == t[j] 时，以s = "rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。
		 *
		 * 此时分为2种情况，s串用最后一位的a + 不用最后一位的a。
		 *
		 * 如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
		 *
		 * 如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
		 *
		 * 所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
		 *
		 * 再看s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
		 *
		 * 此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
		 *
		 * 所以此时dp[i][j] = dp[i-1][j]
		 */
		int m = s.length(),n = t.length();
		int[][] dp = new int[m+1][n+1];//dp[i][j]：前 i 个字符的 s 子串中，出现前 j 个字符的 t 子串的次数。
		//初始化
		for (int i = 0; i <= m; i++) {
			dp[i][0] = 1;
		}
		for (int i = 1; i <= m ; i++) {
			for (int j = 1; j <=n; j++) {
				if(s.charAt(i-1) == t.charAt(j-1)){
					dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
				}else{
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		return dp[m][n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
